# 栈 stack
"""
后进者先出，先进者后出，这就是典型的“栈”结构。
"""


# 操作的时间、空间复杂度
"""
不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
注意，这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。
所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
空间复杂度分析是不是很简单？时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。
"""


# 栈的实现


# 基于数组实现栈
# python基本数据中只有列表，所以基本用列表来代替数组
class ArrayStack(object):
    def __init__(self):
        self.items = []

    # 入栈
    def push(self, item):
        self.items.append(item)

    # 出栈
    def pop(self):
        if self.items:
            self.items.pop()


# 基于链表实现栈
# 节点
class Node(object):
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


# {'data': 1, 'next':{'data':2, 'next': None}}
class LinkedStack(object):
    def __init__(self):
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        if self.top:
            self.top = self.top.next

    def __repr__(self):
        nums = []
        p = self.top
        while p:
            nums.append(str(p.data))
            p = p.next
        return " ".join(nums)


if __name__ == '__main__':
    print("*" * 10 + "栈")
    stack = LinkedStack()
    for i in range(9):
        stack.push(i)
    print(stack)
